//对于字符串 s 和 t，只有在 s = t + ... + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。 
//
// 给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 x 能除尽 str2 。 
//
// 
//
// 示例 1： 
//
// 
//输入：str1 = "ABCABC", str2 = "ABC"
//输出："ABC"
// 
//
// 示例 2： 
//
// 
//输入：str1 = "ABABAB", str2 = "ABAB"
//输出："AB"
// 
//
// 示例 3： 
//
// 
//输入：str1 = "LEET", str2 = "CODE"
//输出：""
// 
//
// 
//
// 提示： 
//
// 
// 1 <= str1.length, str2.length <= 1000 
// str1 和 str2 由大写英文字母组成 
// 
//
// Related Topics 数学 字符串 👍 356 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2023-09-23 15:23:04
 * @description 1071.字符串的最大公因子
 */
public class GreatestCommonDivisorOfStrings{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new GreatestCommonDivisorOfStrings().new Solution();
		solution.gcdOfStrings("abcabc","abc");
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //枚举
    public String gcdOfStrings(String str1, String str2) {
		int m = str1.length();
		int n=str2.length();
		if (m<n){
			String temp = str1;
			str1 = str2;
			str2 = temp;
		}
		int min=Math.min(m,n);
		if(check(str1,str2,str2)){
			return str2;
		}
		min/=2;
		while (min>0){
			if(check(str1,str2,str2.substring(0,min))){
				return str2.substring(0,min);
			}
			min--;
		}
		return "";
	}
	private  boolean check(String str1, String str2,String str){
			if(str1.length()%str.length()==0&&str2.length()%str.length()==0){
				for (int i = 0; i < str1.length(); i+=str.length()) {
					if(!str1.substring(i).startsWith(str)){
						return false;
					}
				}
				for (int i = 0; i < str2.length(); i+=str.length()) {
					if(!str2.substring(i).startsWith(str)){
						return false;
					}
				}
				return true;
			}

			return false;
	}

	//直接用公约数检查  时间空间On
	public String gcdOfStrings1(String str1, String str2) {
		int m = str1.length();
		int n=str2.length();
		String t=str1.substring(0,gcd(m,n));
		if(check1(t,str2)&&check1(t,str1)){
			return t;
		}
		return "";
	}
	private boolean check1(String t,String s){
		for (int i = 0; i < s.length(); i+=t.length()) {
			if(!s.substring(i).startsWith(t)){
				return false;
			}
		}
		return true;
	}
	private int gcd(int a,int b){
		int t=a%b;
		while (t!=0){
			a=b;
			b=t;
			t=a%b;
		}
		return b;
	}

	//数学
	public String gcdOfStrings2(String str1, String str2) {
		if (!str1.concat(str2).equals(str2.concat(str1))) {
			return "";
		}
		return str1.substring(0, gcd(str1.length(), str2.length()));
	}


}
//leetcode submit region end(Prohibit modification and deletion)

}
